package jianzhiOffer;
//剑指 Offer 36. 二叉搜索树与双向链表
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }
    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
public class Num36_treeToDoublyList {
    //定义头节点和前驱节点
    Node pre,head;
    public Node treeToDoublyList(Node root) {
        if (root == null){
            return null;
        }
        //双端队列
        dfs(root);
        //此时pre指向尾结点
        head.left = pre;
        pre.right = head;
        return head;
    }
    //传一个树的根节点，转换成双向链表
    void dfs(Node cur){
        //递归出口
        if (cur == null){
            return;
        }
        dfs(cur.left);
        if (pre != null){
            pre.right = cur;
        }else {
            //没有根节点
            head = cur;
        }
        cur.left = pre;//连接左节点
        pre = cur; // 节点后移
        dfs(cur.right);//递归处理右子树

    }
}
